#define _CRT_SECURE_NO_WARNINGS
#include"图.h"
#include"队列.h"
void Init(graph *ps)
{
	for (int i = 0; i < MAXVEX; i++)
	{
		ps->visted[i] = 0;
		for (int j = 0; j < MAXVEX; j++)
		{
			ps->arc[i][j] = INF;
		}
	}
}

void Creat(graph* ps)
{
	int i, j, k, w;
	printf("请输入顶点数和边数\n");
	scanf("%d %d", &ps->vexnum, &ps->edgenum);
	Init(ps);
	printf("请输入顶点信息\n");
	for (int i = 0; i < ps->vexnum; i++)
	{
		ps->Vertex[i] = i;//储存序号
		while (getchar() != '\n');
		scanf("%c", &ps->Vername[i]);//输入顶点的名字
	}
	for (k = 0; k <ps->edgenum; k++)
	{
		printf("请输入边（vi,vj）的下标 i和j以及权值w:");
		scanf("%d %d %d", &i, &j, &w);
		ps->arc[i][j] = ps->arc[j][i] = w;
	}
}

void Print(graph* ps)
{
	printf("邻接矩阵\n");
	for (int i = 0; i < ps->vexnum; i++)
	{
		for (int j = 0; j <ps->vexnum; j++)
		{
			printf("%4d", ps->arc[i][j]);
		}
		printf("\n");
	}
}

int LocateVex(graph* ps, char ch)
{
	int i = 0;
	for ( i = 0; i < MAXVEX; i++)
	{
		if (ch == ps->Vername[i])
		{
			return i;
		}
	}
	if (i == MAXVEX)
	{
		return -1;
	}
}

void InserVex(graph* ps, char ch)
{
	ps->Vertex[ps->vexnum] = ps->vexnum;
	ps->Vername[ps->vexnum] = ch;
	ps->vexnum++;
}

void InsetEdge(graph* ps, int i, int j, int w)
{
	ps->arc[i][j] = w;
	ps->edgenum++;
}

void  DeleteEdge(graph* ps, int i, int j)
{
	ps->arc[i][j] = INF;
	ps->edgenum--;
}

void DeleteVex(graph* ps, char ch)
{
	int i = 0;
	for ( i = 0; i < ps->vexnum; i++)
	{
		if (ps->Vername[i] == ch)
		{
			break;
		}
	}
	//vername数组左移
	for (int j = i; j < ps->vexnum-1; j++)
	{
		ps->Vername[j] = ps->Vername[j + 1];
	}
	//数组循环左移
	for (int j = i; j < ps->vexnum - 1; j++)
	{
		for (int k = 0; k < ps->vexnum; k++)
		{
			ps->arc[j][k] = ps->arc[j + 1][k];
		}
	}
	//数组右移
	for (int i = 0; i < ps->vexnum - 1; i++)
	{
		for (int k = i; k < ps->vexnum - 1; k++)
		{
			ps->arc[i][k] = ps->arc[i][k + 1];
		}
	}
	ps->vexnum--;
}

char FirstAdjvex(graph* ps, char ch)
{
	int i, j;
	for (i = 0; i < ps->vexnum; i++)
	{
		if (ch == ps->Vername[i])
		{
			break;
		}
	}
	for (j = 0; j < ps->vexnum; j++)
	{
		if (ps->arc[i][j] != INF)
		{
			break;
		}
	}
	if (j == ps->vexnum)
	{
		return '\0';
	}
	else
	{
		return ps->Vername[j];
	}
}

void DNS(graph* ps, char ch)
{
	int i, j;
	int l = LocateVex(ps, ch);
	printf("%c ", ps->Vername[l]);//输出当前节点
	ps->visted[l] = 1;//表示已经访问过
	for (i = 0; i < ps->vexnum; i++)
	{
		if (ps->visted[i] == 0 && ps->arc[l][i] != INF)
		{
			DNS(ps,ps->Vername[i]);
		}
	}

}

void BFS(graph* ps, char ch)
{
	Queue q;
	QueueInit(&q);
	int l = LocateVex(ps, ch);
	printf("%c ", ps->Vername[l]);
	QueuePush(&q, l);
	ps->visted[l] = 1;//表示已经访问过
	while (QueueSize(&q))
	{
		l = QueueFront(&q);
		QueuePop(&q);
		for (int i = 0; i < ps->vexnum; i++)
		{
			if (ps->visted[i] == 0 && ps->arc[l][i] != INF)
			{
				printf("%c ", ps->Vername[i]);
				QueuePush(&q, i);
				ps->visted[i] = 1;
			}
		}
	}

}
int main()
{
	graph s;
	Creat(&s);
	Print(&s);
	//int m = LocateVex(&s, 'c');
	//printf("%d",m);
	//InserVex(&s, 'g');
	//DeleteVex(&s, 'c');
	//Print(&s);
	//char m=FirstAdjvex(&s, 'c');
	//printf("%c", m);
	//printf("深度优先遍历：\n");
	while (getchar() != '\n');
	printf("请输入顶点的信息\n");
	char ch = getchar();
	BFS(&s, ch);
	return 0;
}

//5 6
//a
//b
//c
//d
//e
//0 1 9
//0 2 2
//0 4 6
//1 2 3
//2 3 5
//3 4 1

//9 10
//0
//1
//2
//3
//4
//5
//6
//7
//8
//0 1 1
//0 2 1
//1 3 1
//1 4 1
//2 5 1
//2 6 1
//3 7 1
//4 7 1
//5 6 1
//7 8 1